package woa.linkedlist;

/**
 * 扁平化多级双向链表
 * 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有
 * 一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。
 * 给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。
 * <p>
 * 输入：head = [1,2,null,3]
 * 输出：[1,3,2]
 * 解释：
 * 输入的多级列表如下图所示：
 * <p>
 * 1---2---NULL
 * |
 * 3---NULL
 *
 * @author wangpeng
 * @date 2021/11/22
 */
public class FlattenProblem {

    static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;

        public Node(int val) {
            this.val = val;
        }
    }

    public static Node flatten(Node head) {
        dfs(head);
        return head;
    }

    public static Node dfs(Node node) {
        Node cur = node;
        while (cur != null && (cur.next != null || cur.child != null)) {

            if (cur.child != null) {
                Node tail = dfs(cur.child);
                tail.next = cur.next;
                if (cur.next != null) {
                    cur.next.prev = tail;
                }
                cur.next = cur.child;
                cur.child.prev = cur;
                cur.child = null;
            } else {
                cur = cur.next;
            }
        }

        return cur;
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        node1.child = node2;
        Node node3 = new Node(3);
        node2.child = node3;
        flatten(node1);
    }
}
